#include <iostream>
#include <vector>
using namespace std;

int minPathSum(vector<vector<int> > &grid) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int height = grid.size();
    if(height == 0)
        return 0;
    int width = grid[0].size();
    if(width == 0)
        return 0;

    int *pRead = new int[width];
    int *pWrite = new int[width];
    // init first line
    pRead[0] = grid[0][0];
    for(int j=1; j<width; ++j){
        pRead[j] = pRead[j-1] + grid[0][j];
    }
    // other
    for(int i=1; i<height; ++i){
        pWrite[0] = pRead[0] + grid[i][0];
        for(int j=1; j<width; ++j){
            pWrite[j] = (pWrite[j-1] > pRead[j] ? pRead[j] : pWrite[j-1]) + grid[i][j];
        }
        int *pTmp = pWrite;
        pWrite = pRead;
        pRead = pTmp;
    }
    int res = pRead[width-1];
    delete []pRead;
    delete []pWrite;
    return res;
}



int main(){
    return 0;
}